「CF311B」 Cats Transport

发表于 | 分类于 | | 浏览量： 次

喵喵喵，斜率优化带猫猫早早回家。

传送门

洛谷

CF311B

题解

首先定义：

其中要先对A数组从小到大排序再计算前缀和。这样每个饲养员带走的必定为连续的几只猫。

定义$F[i][j]$表示前$i$个饲养员带走了前$j$只猫时的最小等待时间之和。转移方程为：

但是直接这样转移的话复杂度太高，考虑斜率优化。可以把转移方程写成直线的形式：

这样就可以把$F[i-1][k]+S[k]$看作纵坐标，$k$看作横坐标，$A[j]$看成斜率。然后用单调队列维护一个斜率递增的下凸壳就行了。

代码

挺短的QwQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;const LL inf=0x3F3F3F3F3F3F3F3Fll;
int n,m,P,H[maxn],D[maxn],T[maxn],A[maxn],que[maxn],hed,til;LL S[maxn],F[105][maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main()
{
	n=read();m=read();P=read();
	for(int i=2;i<=n;i++) D[i]=D[i-1]+read();
	for(int i=1;i<=m;i++)
	{
		H[i]=read();
		T[i]=read();
		A[i]=T[i]-D[H[i]];
	}
	sort(A+1,A+1+m);
	for(int i=1;i<=m;i++) S[i]=S[i-1]+A[i];
	for(int i=1;i<=m;i++) F[0][i]=inf;
	for(int i=1;i<=P;i++)
	{
		hed=til=1;que[1]=0;
		for(int j=1;j<=m;j++)
		{
			while(hed>til&&(F[i-1][que[til+1]]+S[que[til+1]]-F[i-1][que[til]]-S[que[til]])<=(LL)A[j]*(que[til+1]-que[til])) til++;
			F[i][j]=F[i-1][que[til]]+(LL)A[j]*(j-que[til])-(S[j]-S[que[til]]);
			while(hed>til&&(F[i-1][j]+S[j]-F[i-1][que[hed]]-S[que[hed]])*(que[hed]-que[hed-1])<=(F[i-1][que[hed]]+S[que[hed]]-F[i-1][que[hed-1]]-S[que[hed-1]])*(j-que[hed])) hed--;
			que[++hed]=j;
		}
	}
	printf("%lld\n",F[P][m]);
	return 0;
}